package book;
// ref: LC452

import java.util.Arrays;

public class StationSolution {
    // 表示需求区间的对象类
    // 排序时先根据左边界排序，再根据右边界
    class RequestRange implements Comparable<RequestRange> {
        final int left, right; // 左右边界

        RequestRange(int l, int r) {
            left = l; right = r;
        }

        @Override
        public int compareTo(RequestRange o) {
            int cr = Integer.compare(left, o.left);
            if (cr == 0)
                cr = Integer.compare(right, o.right);
            return cr;
        }
    }

    // 使用排序+贪心求最小建设基站数量
    public int minStations(int[][] ranges) {
        // 边界判断：一个需求都没有那就返回0
        if (ranges == null || ranges.length == 0) 
            return 0;

        // 将输入转换成对象数组，然后排序
        RequestRange[] arr = new RequestRange[ranges.length];
        for (int i = 0; i < ranges.length; i++)
            arr[i] = new RequestRange(ranges[i][0], ranges[i][1]);
        Arrays.sort(arr);

        // 每一座基站在尽可能多覆盖需求的前提下尽可能放右边，
        // 用minRight维护当前基站可以建设的最远（右）位置
        int n = 1, minRight = arr[0].right;
        for (RequestRange r: arr) {
            if (r.left > minRight) {
                n++;
                minRight = r.right;
            } else {
                minRight = Math.min(minRight, r.right);
            }
        }

        return n;
    }

    public static void main(String[] args) {
        int[][] ranges = { {1, 4}, {2, 3}, {4, 5} };
        int n = new StationSolution().minStations(ranges);
        System.out.println("基站数目: " + n);
    }
}
